package 二叉树相关问题.经典二叉树问题;


public class 从前序遍历和后序遍历构造二叉树 {

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        return buildTree(pre,0,pre.length-1,post,0,post.length-1);
    }

    private TreeNode buildTree(int[] pre, int prestart, int preend, int[] post, int poststart, int postend) {
        if (preend<prestart || poststart>postend)
            return null;
        if (prestart==preend)
            return new TreeNode(pre[prestart]);
        int left = pre[prestart+1];
        int index=0;
        //找到左子树的大小
        for (int i = poststart; i <= postend; i++) {
            if (post[i]==left)
                index=i;
        }
        int leftLength=index-poststart;
        TreeNode root = new TreeNode(pre[prestart]);
        root.left=buildTree(pre,prestart+1,prestart+leftLength+1,post,poststart,index);
        root.right=buildTree(pre,prestart+leftLength+2,preend,post,index+1,postend-1);
        return root;
    }
}
